<?php


namespace XiaoGuai\DataStructure\Queue\LinkedQueue;


use XiaoGuai\DataStructure\Queue\QueueInterface;
use XiaoGuai\DataStructure\Queue\LinkedQueue\LinkedQueueNode as Node;

class LinkedQueue implements QueueInterface
{

    /**
     *
     *   头                   尾
     *   [] -> A -> B -> C -> D
     * front                 rear
     *        消费(删除A结点)
     *   头                   尾
     *   [] - - -> B -> C -> D
     * front                 rear
     */

    /**
     * @var null|Node 头指针
     */
    protected $front = null;

    /**
     * @var null|Node 尾指针
     */
    protected $rear = null;

    /**
     * @var int 存储元素长度
     */
    protected $length = 0;

    /**
     * 构造一个空队列
     * QueueInterface constructor.
     */
    public function __construct()
    {
        $this->front = new Node();
        $this->front->next = null;
        $this->rear = $this->front;
        $this->length = 0;
    }

    /**
     * 队列元素是否为空,队头消费完了元素
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->front === $this->rear;
    }

    /**
     * 队列元素长度
     * @return int
     */
    public function length(): int
    {
        return $this->length;
    }

    /**
     * 队列顶部元素
     * @return mixed
     */
    public function top()
    {
        if ($this->front === $this->rear) {
            throw new \Exception('overflow');
        }
        return $this->front->next->data;
    }

    /**
     * 入队,队尾插入元素
     * @param $element
     * @return bool
     */
    public function enqueue($element): bool
    {
        $node = new Node();
        $node->data = $element;

        $node->next = $this->rear->next;
        $this->rear->next = $node;
        $this->rear = $node;
    }

    /**
     * 出队, 队头消费元素(删除front的next结点)
     * @return mixed
     */
    public function dequeue()
    {
        if ($this->front === $this->rear) {
            throw new \Exception('overflow');
        }

        $p = $this->front->next;
        $element = $p->data;
        $this->front->next = $p->next;

        if ($p === $this->rear) {
            // 如果消费的是rear,则将rear指向front[等价于空队列]
            $this->rear = $this->front;
        }
        unset($p);
        return $element;
    }
}